package com.cdream.basic.algorithm.leetcode.array;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cdream
 * @date 2022/3/9
 */
public class Question238 {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] left = new int[len];
        int[] right = new int[len];
        for(int i = 0; i<len;i++){
            if(i==0){
                left[i] = nums[i];
                right[len-i-1] = nums[len-i-1];
            }else{
                left[i] = left[i-1]*nums[i];
                right[len-i-1] = right[len-i] * nums[len-i-1];
            }
        }
        int[] res = new int[len];
        for(int i = 0; i<len; i++){
            int l = i==0?1:left[i-1];
            int r = i ==len-1?1:right[i+1];
            res[i] = l * r;
        }
        return res;
    }

    public static void main(String[] args) {
        // new Question238().productExceptSelf(new int[]{1,2,3,4});
        // System.out.println(Arrays.toString("狗".getBytes()));
        for (byte b : "鲲".getBytes()) {
            System.out.println(b);
            System.out.println(Integer.toBinaryString(b));
        }
    }

}
class Solution {
    List<Integer>[] children;
    long maxScore =0;
    int cnt = 0;
    int n;
    public int countHighestScoreNodes(int[] parents) {
        n = parents.length;
        children = new List[parents.length];
        children[0] = new ArrayList<>();
        for(int i = 1;i<parents.length; i++){
            // 获取父节点
            int p = parents[i];
            List<Integer> child = children[p];
            if(child==null){
                children[p] = new ArrayList<Integer>();
            }
            child = children[p];
            child.add(i);
        }
        dfs(0);
        return cnt;
    }
    int dfs(int node){
        long score = 1;
        int remain = n -1;
        for(int child : children[node]){
            int childCnt = dfs(child);
            remain -=childCnt;
            score *= childCnt;
        }
        if(node!=0){
            score*=remain;
        }
        if(score > maxScore){
            maxScore =score;
            cnt = 1;
        }else if(score==maxScore){
            cnt += 1;
        }
        return n - remain -1;
    }
}
